﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
using namespace std;
int pivotIndex(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n), g(n);
    for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] + nums[i - 1];
    }
    for (int i = n - 2; i >= 0; i--) {
        g[i] = g[i + 1] + nums[i + 1];
    }
    for (int i = 0; i < n; i++) {
        if (f[i] == g[i])
            return i;
    }
    return -1;
}

const int kmod = 1000000007;  // 定义模数

// 主函数：计算逆序对数目
int InversePairs(vector<int> data) {
    int ret = 0;  // 存储结果
    vector<int> tmp(data.size());  // 提前分配临时数组，避免递归中反复创建
    mergeSort(data, tmp, 0, data.size() - 1, ret);  // 调用归并排序
    return ret;
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, vector<int>& tmp, int l, int r, int& ret) {
    if (l >= r) return;  // 递归终止条件：子数组长度为1或空

    int mid = l + ((r - l) >> 1);  // 计算中间点，防止溢出
    mergeSort(arr, tmp, l, mid, ret);    // 递归左半部分
    mergeSort(arr, tmp, mid + 1, r, ret); // 递归右半部分
    merge(arr, tmp, l, mid, r, ret);      // 合并左右两部分并统计逆序对
}

// 合并函数：统计逆序对并合并有序数组
void merge(vector<int>& arr, vector<int>& tmp, int l, int mid, int r, int& ret) {
    int i = l;       // 左半部分起始指针
    int j = mid + 1; // 右半部分起始指针
    int k = 0;       // 临时数组指针

    while (i <= mid && j <= r) {  // 遍历左右子数组
        if (arr[i] > arr[j]) {    // 左元素 > 右元素，发现逆序对
            tmp[k++] = arr[j++];  // 将较小元素（右）放入临时数组
            // 左半部分剩余元素都 > 当前右元素，累加逆序对数目
            ret += (mid - i + 1);
            ret %= kmod;  // 取模防止溢出
        }
        else {  // 左元素 <= 右元素，无逆序对
            tmp[k++] = arr[i++];  // 放入左元素
        }
    }

    // 处理剩余元素
    while (i <= mid) tmp[k++] = arr[i++];  // 左半剩余元素
    while (j <= r) tmp[k++] = arr[j++];    // 右半剩余元素

    // 将临时数组中的有序结果复制回原数组
    for (k = 0, i = l; i <= r; ++i, ++k) {
        arr[i] = tmp[k];
    }
}

int findMin(vector<int>& nums)
{
    int left = 0, right = nums.size() - 1;
    int x = nums[right]; // 标记⼀下最后⼀个位置的值
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] > x) left = mid + 1;
        else right = mid;
    }
    return nums[left];
}
int minNumberInRotateArray(vector<int>& nums) {
    // write code here
    int left = 0;
    int right = nums.size() - 1;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) left = mid + 1;
        else if (nums[mid] == nums[right]) right--;
        else right = mid;
    }
    return nums[left];
}

int compare(string version1, string version2) {
    // write code here
    int len1 = version1.size();
    int len2 = version2.size();
    int i = 0;
    int j = 0;
    while (i < len1 || j < len2) {
        long x = 0;
        long y = 0;
        while (i < len1 && version1[i] != '.') {
            x = x * 10 + (version1[i] - '0');
            ++i;
        }
        ++i;
        while (j < len2 && version2[j] != '.') {
            y = y * 10 + (version2[j] - '0');
            ++j;
        }
        ++j;
        if (x > y) {
            return 1;
        }
        else if (x < y) {
            return -1;
        }
    }
    return 0;
}

int maxSubArray(vector<int>& nums) {
    // 处理边界条件：若数组为空，根据题意应不存在此情况，但假设返回0
    if (nums.empty())
        return 0;
    int current_max = nums[0]; // 当前子数组的最大和，初始为第一个元素
    int global_max = nums[0];  // 全局最大子数组和，初始同current_max

    // 从第二个元素开始遍历数组
    for (int i = 1; i < nums.size(); ++i) {
        // 决定当前子数组是延续之前的和还是从当前元素重新开始
        // 如果之前的current_max是负数，nums[i]加上它会更小，所以直接取nums[i]
        current_max = max(nums[i], current_max + nums[i]);
        // 更新全局最大值，保持最大的子数组和
        global_max = max(global_max, current_max);
    }

    return global_max;
}
vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> lprod(n + 1), rprod(n + 1);
    lprod[0] = 1, rprod[n - 1] = 1;
    // 预处理前缀积以及后缀积
    for (int i = 1; i < n; i++)
        lprod[i] = lprod[i - 1] * nums[i - 1];
    for (int i = n - 2; i >= 0; i--)
        rprod[i] = rprod[i + 1] * nums[i + 1];
    // 处理结果数组
    vector<int> ret(n);
    for (int i = 0; i < n; i++)
        ret[i] = lprod[i] * rprod[i];
    return ret;
}